package com.cb2.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/'>填充每个节点的下一个右侧节点指针(Populating Next Right Pointers in Each Node)</a>
 * <p>
 * 给定一个<b>完美二叉树</b> ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 * <pre>
 *  struct Node {
 *      int val;
 *      Node *left;
 *      Node *right;
 *      Node *next;
 *  }
 * </pre>
 * </p>
 * <p>填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。</p>
 * <p>初始状态下，所有 next 指针都被设置为 NULL。</p>
 * <p>
 * <b>示例：</b>
 * <pre><a href='https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/'>查看示例</a></pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>树中节点的数量在 [0, 2^12 - 1] 范围内</li>
 *      <li>-1000 <= node.val <= 1000</li>
 *  </ul>
 * </p>
 * <b>进阶：</b>
 * <ui>
 * <li>你只能使用常量级额外空间。</li>
 * <li>使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。</li>
 * </ui>
 *
 * @author c2b
 * @see LC0116PopulatingNextRightPointersInEachNode_I_M 填充每个节点的下一个右侧节点指针 I
 * @see LC0117PopulatingNextRightPointersInEachNode_II_M 填充每个节点的下一个右侧节点指针 II
 * @since 2025/2/8 14:20
 */
public class LC0116PopulatingNextRightPointersInEachNode_I_M {

    static class Solution {
        public Node connect(Node root) {
            // 不使用额外空间
            return connect1(root);
            // 使用额外空间：队列
            //return connect2(root);
        }

        private Node connect1(Node root) {
            if (root == null) {
                return null;
            }
            Node currLevelLeftmostNode = root;
            while (currLevelLeftmostNode.left != null) {
                Node currNode = currLevelLeftmostNode;
                while (currNode != null) {
                    // 当前节点的左子节点的next指向当前节点的右子节点
                    currNode.left.next = currNode.right;
                    // 用于处理不同父节点的节点，即当前节点的右子节点：当前节点的右子节点的next指向当前节点的next节点的左子节点
                    if (currNode.next != null) {
                        currNode.right.next = currNode.next.left;
                    }
                    // 进入同一层的下一个节点，即当前节点的右侧节点
                    currNode = currNode.next;
                }
                // 进入下一层的最左节点
                currLevelLeftmostNode = currLevelLeftmostNode.left;
            }
            return root;
        }

        private Node connect2(Node root) {
            if (root == null) {
                return null;
            }
            Queue<Node> helper = new LinkedList<>();
            helper.offer(root);
            while (!helper.isEmpty()) {
                int currLevelNodeSize = helper.size();
                Node prevNode = null;
                for (int i = 0; i < currLevelNodeSize; i++) {
                    Node currNode = helper.poll();
                    currNode.next = prevNode;
                    prevNode = currNode;
                    if (currNode.right != null) {
                        helper.offer(currNode.right);
                    }
                    if (currNode.left != null) {
                        helper.offer(currNode.left);
                    }
                }

            }
            return root;
        }

        private static class Node {
            public int val;
            public Node left;
            public Node right;
            public Node next;

            public Node() {
            }

            public Node(int _val) {
                val = _val;
            }

            public Node(int _val, Node _left, Node _right, Node _next) {
                val = _val;
                left = _left;
                right = _right;
                next = _next;
            }
        }
    }

    public static void main(String[] args) {
        Solution.Node root = new Solution.Node(1);
        root.left = new Solution.Node(2);
        root.right = new Solution.Node(3);
        root.left.left = new Solution.Node(4);
        root.left.right = new Solution.Node(5);
        root.right.left = new Solution.Node(6);
        root.right.right = new Solution.Node(7);

        Solution solution = new Solution();
        Solution.Node connect = solution.connect(root);
    }
}
